#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,K,a[100005],Q,t1,t2,t3,ans,dp[100005],ch[100005][2],dp2[100005]; 
stack<int> q;
struct ok{
	int x,y;
};
vector<ok> e;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
inline void solve1(){
	for(int i=1;i<=Q;i++){
		t1=read(),t2=read(),t3=read();
		swap(a[t1],a[t1+1]);
		ans=0;
		for(int j=1;j<=n;j++){
			while(!q.empty()&&a[q.top()]<=a[j]) q.pop();
			if(q.empty()) ch[j][0]=1;
			else ch[j][0]=q.top()+1;
			q.push(j);
		}
		while(!q.empty()) q.pop();
		for(int j=n;j>=1;j--){
			while(!q.empty()&&a[q.top()]<=a[j]) q.pop();
			if(q.empty()) ch[j][1]=n;
			else ch[j][1]=q.top()-1;
			q.push(j);
		}
		while(!q.empty()) q.pop();
		for(int j=1;j<=n;j++) dp[j]=-1;
		for(int j=1;j<=n;j++){
			if(dp[j]==-1){
				e.clear();e.push_back((ok){j,0});
				int l=j,r=j,v=j;
				while(l!=1||r!=n){
					l=ch[v][0];
					r=ch[v][1];
					if(l!=1||r!=n){
						if(a[l-1]<a[r+1]) e.push_back((ok){l-1,0}),v=l-1;
						else if(a[l-1]>a[r+1]) e.push_back((ok){r+1,0}),v=r+1;
						else e.push_back((ok){l-1,r+1}),v=l-1;
					}
				}
				for(int g=0;g<(int)e.size();g++){
					dp[e[g].x]=(int)e.size()-1-g;
					if(e[g].y) dp[e[g].y]=(int)e.size()-1-g;
				}
			}
		}
		for(int j=t2;j<=t3;j++) ans+=(dp[j]*K+n-1);
		cout<<ans<<"\n";
	}
}
inline void solve2(){
	int o=read();
	for(int j=1;j<=n;j++){
			while(!q.empty()&&a[q.top()]<=a[j]) q.pop();
			if(q.empty()) ch[j][0]=1;
			else ch[j][0]=q.top()+1;
			q.push(j);
		}
		while(!q.empty()) q.pop();
		for(int j=n;j>=1;j--){
			while(!q.empty()&&a[q.top()]<=a[j]) q.pop();
			if(q.empty()) ch[j][1]=n;
			else ch[j][1]=q.top()-1;
			q.push(j);
		}
		while(!q.empty()) q.pop();
		for(int j=1;j<=n;j++) dp[j]=-1;
		for(int j=1;j<=n;j++){
			if(dp[j]==-1){
				e.clear();e.push_back((ok){j,0});
				int l=j,r=j,v=j;
				while(l!=1||r!=n){
					l=ch[v][0];
					r=ch[v][1];
					if(l!=1||r!=n){
						if(a[l-1]<a[r+1]) e.push_back((ok){l-1,0}),v=l-1;
						else if(a[l-1]>a[r+1]) e.push_back((ok){r+1,0}),v=r+1;
						else e.push_back((ok){l-1,r+1}),v=l-1;
					}
				}
				for(int g=0;g<(int)e.size();g++){
					dp[e[g].x]=(int)e.size()-1-g;
					if(e[g].y) dp[e[g].y]=(int)e.size()-1-g;
				}
			}
		}
	swap(a[o],a[o+1]);
	for(int j=1;j<=n;j++){
			while(!q.empty()&&a[q.top()]<=a[j]) q.pop();
			if(q.empty()) ch[j][0]=1;
			else ch[j][0]=q.top()+1;
			q.push(j);
		}
		while(!q.empty()) q.pop();
		for(int j=n;j>=1;j--){
			while(!q.empty()&&a[q.top()]<=a[j]) q.pop();
			if(q.empty()) ch[j][1]=n;
			else ch[j][1]=q.top()-1;
			q.push(j);
		}
		while(!q.empty()) q.pop();
		for(int j=1;j<=n;j++) dp2[j]=-1;
		for(int j=1;j<=n;j++){
			if(dp2[j]==-1){
				e.clear();e.push_back((ok){j,0});
				int l=j,r=j,v=j;
				while(l!=1||r!=n){
					l=ch[v][0];
					r=ch[v][1];
					if(l!=1||r!=n){
						if(a[l-1]<a[r+1]) e.push_back((ok){l-1,0}),v=l-1;
						else if(a[l-1]>a[r+1]) e.push_back((ok){r+1,0}),v=r+1;
						else e.push_back((ok){l-1,r+1}),v=l-1;
					}
				}
				for(int g=0;g<(int)e.size();g++){
					dp2[e[g].x]=(int)e.size()-1-g;
					if(e[g].y) dp2[e[g].y]=(int)e.size()-1-g;
				}
			}
		}
	for(int i=1;i<=n;i++) dp[i]+=dp[i-1],dp2[i]+=dp2[i-1];
	for(int i=1;i<=Q;i++){
		if(i==1) t2=read(),t3=read();
		else t1=read(),t2=read(),t3=read();
		if(i&1){
			int d1=dp2[t3]-dp2[t2-1];
			int d2=d1*K+(n-1)*(t3-t2+1);
			cout<<d2<<"\n";
		}
		else{
			int d1=dp[t3]-dp[t2-1];
			int d2=d1*K+(n-1)*(t3-t2+1);
			cout<<d2<<"\n";
		}
	}
}
signed main(){
	freopen("summer.in","r",stdin);
	freopen("summer.out","w",stdout);
	n=read(),K=read();
	for(int i=1;i<=n;i++) a[i]=read();
	a[0]=a[n+1]=1e18;
	Q=read();
	if(n<=1000&&Q<=1000) solve1();
	else solve2();
	return 0;
}

